package 动态规划;

/**
 * @description:
 * @author: ywk
 * @date: 2020-10-28
 */
public class 最长公共子串 {
    /**
     * longest common substring
     * @return string字符串
     */

    public static void main(String[] args) {
        System.out.println(LCS("1AB2345CD", "12345EF"));
        System.out.println(dp("1AB2345CD", "12345EF"));
    }

    /**
     * "1AB2345CD","12345EF" "2345"
     *
     * @param str1
     * @param str2
     * @return
     */
    public static String LCS(String str1, String str2) {
        String maxVal = "";
        if (str1 == null || str2 == null || str1.length() == 0 || str2.length() == 0) {
            return maxVal;
        }
        int sLength = str1.length();
        int tLength = str2.length();
        //str1为较长的一位
        int i = 0, j = 0;
        while (j < str2.length()) {
            String substring = str2.substring(i, j);
            if (str1.contains(substring)) {
                if (substring.length() > maxVal.length()) {
                    maxVal = substring;
                }
                j++;
            } else {
                i++;
            }
        }
        return maxVal;
    }

    public static String dp(String str1, String str2) {
        int m = str1.length();
        int n = str2.length();
        int[][] dp = new int[m + 1][n + 1];
        int maxLen = 0, endPos = 0;
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    if (dp[i][j] > maxLen) {
                        maxLen = dp[i][j];
                        endPos = i - 1;
                    }
                }
            }
        }
        return str1.substring(endPos - maxLen + 1, endPos + 1);
    }
}
